package com.fzkj.algorithm;

public class IsSubsequence {

    /**
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     *
     * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
     *
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     *
     * 示例 1:
     * s = "abc", t = "ahbgdc"
     *
     * 返回 true.
     *
     * 示例 2:
     * s = "axc", t = "ahbgdc"
     *
     * 返回 false.
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/is-subsequence
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    // 我的解题思路
    /**
     * 1.遍历s，并在t中比较，返回下标
     */


    /**
     * 这样，我们初始化两个指针 ii 和 jj，分别指向 ss 和 tt 的初始位置。每次贪心地匹配，匹配成功则 ii 和 jj 同时右移，匹配 ss 的下一个位置，匹配失败则 jj 右移，ii 不变，尝试用 tt 的下一个字符匹配 ss。
     *
     * 最终如果 ii 移动到 ss 的末尾，就说明 ss 是 tt 的子序列。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/is-subsequence/solution/pan-duan-zi-xu-lie-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    public static void main(String[] args) {

        String t = "ahbgdc";
//        String s = "abc";
        String s = "axc";
        boolean isSub = isSubsequence(s, t);
        System.out.println(isSub);
    }

    public static boolean isSubsequence(String s, String t){

        int i = 0, j = 0;
        int n = s.length(), m = t.length();
        while(i < n && j <m){
            if (s.charAt(i) == t.charAt(j)){ // 如果相等，i 的指针向后移
                i ++;
            }
            // 否则， j的指针向后移
            j ++;
        }
        return i == n; // 循环结束后，如果i和n相等，说明s遍历完了


//        String sub = null;
//        int index = 1;
//        int index_tmp = 0;
//        for (int i = 0; i < s.length(); i++) {
//            sub = s.substring(i, i+1);
//            // 返回sub在t中的下标，如果不为-1则表示存在
//            index = t.indexOf(sub);
//            if (-1 != index){
//                if (index >= index_tmp){
//                    index_tmp = index;
//                    continue;
//                }else {
//                    return false;
//                }
//            }else {
//                return false;
//            }
//        }
//        return true;
    }




}
